package com.algorithm.bubble;/*
 *@Author:DOWN
 *@Date:2022/3/15 14:42
 *@Comment:冒泡排序
 */

public class BubbleSort {
    private BubbleSort() {
    }

    public static <E extends Comparable<E>> void sort(E[] data) {
        //@1、 由于@2 j+1少了一个索引区间，则 i+1 冒泡排序双重循环 可少比较一个 区间索引
        for (int i = 0; i + 1 < data.length; i++) {
            //@2、  j 与 j+1 两两比对
            for (int j = 0; j < data.length - i - 1; j++) {
                if (data[j].compareTo(data[j + 1]) > 0) {
                    swap(data, j, j + 1);
                }
            }
        }
    }

    /**
     * 优化 检测是否是可以提前结束排序
     *
     * @param data 元素组
     * @param <E>   泛型
     */
    public static <E extends Comparable<E>> void sort2(E[] data) {
        //@1、 由于@2 j+1少了一个索引区间，则 i+1 冒泡排序双重循环 可少比较一个 区间索引
        for (int i = 0; i + 1 < data.length; i++) {
            //@2、  j 与 j+1 两两比对
            boolean isSwapped = false;
            for (int j = 0; j < data.length - i - 1; j++) {
                if (data[j].compareTo(data[j + 1]) > 0) {
                    swap(data, j, j + 1);
                    isSwapped = true;
                }
            }
            if (!isSwapped) {
                break;
            }
        }
    }

    /**
     * 优化2 直接跳过有序区间
     * @param data 元素组
     * @param <E>   泛型
     */
    public static <E extends Comparable<E>> void sort3(E[] data) {
        //@1、 由于@2 j+1少了一个索引区间，则 i+1 冒泡排序双重循环 可少比较一个 区间索引
        for (int i = 0; i + 1 < data.length; i++) {
            //@2、  j 与 j+1 两两比对
            int lastSwappedIndex = 0;
            for (int j = 0; j < data.length - i - 1; j++) {
                if (data[j].compareTo(data[j + 1]) > 0) {
                    swap(data, j, j + 1);
                    lastSwappedIndex = j + 1;
                }
            }
            i = data.length - lastSwappedIndex;
        }
    }

    private static <E> void swap(E[] arr, int i, int j) {
        E t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }
}
